package com.leetcode.contest;

import java.util.PriorityQueue;

/**
 * @author `RKC`
 * @date 2021/11/10 20:52
 */
@SuppressWarnings("ConstantConditions")
public class LC2033获取单值网格的最小操作数 {

    public static int minOperations(int[][] grid, int x) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>((o1, o2) -> Integer.compare(o2, o1));
        int m = grid.length, n = grid[0].length, size = m * n, k = 0, answer = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++, k++) {
                if (k < size / 2 + 1) {
                    priorityQueue.add(grid[i][j]);
                    continue;
                }
                if (priorityQueue.peek() > grid[i][j]) {
                    priorityQueue.poll();
                    priorityQueue.add(grid[i][j]);
                }
            }
        }
        int medium = priorityQueue.poll();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int val = Math.abs(medium - grid[i][j]);
                if (val % x != 0) {
                    return -1;
                }
                answer += val / x;
            }
        }
        return answer;
    }

    public static void main(String[] args) {
        int[][] grid = {{1, 2}, {3, 4}};
        int x = 2;
        System.out.println(minOperations(grid, x));
    }
}
